package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @author:xufengxiang
 * @date 2023-03-08 19:58
 */
public class Code15 {

    public static List<List<Integer>> threeSum1(int[] nums){
        List<List<Integer>> result = new ArrayList<>();
        int size = nums.length;
        if(size < 3){
            return result;
        }

        Arrays.sort(nums);

        for(int i=0; i< size-2; i++){
            if(nums[i] > 0) {
                break;
            }

            if(i> 0 && nums[i] == nums[i-1]){
                continue;
            }

            int target = -nums[i];
            int left = i+1;
            int right = size-1;

            while(left < right){
                if(nums[left] + nums[right] > target){
                    right --;
                } else if(nums[left] + nums[right] < target){
                    left++;
                }else{
                    List<Integer> cur = new ArrayList<>();
                    cur.add(nums[i]);
                    cur.add(nums[left]);
                    cur.add(nums[right]);
                    result.add(cur);
                    right--;
                    left++;

                    while(left < right && nums[left] == nums[left -1]){
                        left ++;
                    }

                    while(left < right && nums[right] == nums[right +1]){
                        right --;
                    }
                }
            }

        }
        return result;
    }

       public static void main(String[] args) {
        List<List<Integer>> lists = threeSum1(new int[]{-1, 0, 1, 2, -1, -4});
        System.out.println(lists);
    }
}
